743B - Chloe and the sequence - CodeForces Solution


binary search bitmasks constructive algorithms implementation *1200

Please click on ads to support us..

Python Code:

import math

a, k = map(int, input().split())

if k % 2 != 0:
    print(1)
    exit()

if k & k-1 == 0:
    print(int(math.log2(k)) + 1)
    exit()

l = 2 ** math.floor(math.log2(k)) + 1
r = 2 ** math.ceil(math.log2(k)) - 1
center = (l + r) // 2

n = math.floor(math.log2(k))

while center != k:
    if center > k:
        r = center - 1
    else:
        l = center + 1
    
    center = (l + r) // 2
    n -= 1
    
print(n)

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long int
#define ull unsigned long long int
#define nl "\n"
#define MOD 1e9+7
#define pb push_back
#define ppb pop_back
#define dbg(x) cerr<<#x<<"-"<<x<<nl;

/* solve function */
void solve(){
    ll n,k;
    cin>>n>>k;
    ll x = 2;
    int i=1;
    while(x<=pow(2,n)){
        if(k%x == x/2){
            cout<<i<<nl;
            return;
        }
        ++i;
        x *= 2;
    }
    cout<<-1<<nl;
}


/* main function */
int main(){
    clock_t start,end;
    start=clock();
    fast();
    ll t=1;
    ll i=1;
    /* cin>>t; */
    while(t--){
        /* cout<<"Case# "<<i<<": "; */
        solve();
        i++;
    }
    end=clock();
    double time=double(end-start)/double(CLOCKS_PER_SEC);
    cerr<<nl<<"Time: "<<time<<" sec"<<nl;
}


Comments

Submit
0 Comments
More Questions

1490A - Dense Array
1650B - DIV + MOD
1549B - Gregor and the Pawn Game
553A - Kyoya and Colored Balls
1364A - XXXXX
1499B - Binary Removals
1569C - Jury Meeting
108A - Palindromic Times
46A - Ball Game
114A - Cifera
776A - A Serial Killer
25B - Phone numbers
1633C - Kill the Monster
1611A - Make Even
1030B - Vasya and Cornfield
1631A - Min Max Swap
1296B - Food Buying
133A - HQ9+
1650D - Twist the Permutation
1209A - Paint the Numbers
1234A - Equalize Prices Again
1613A - Long Comparison
1624B - Make AP
660B - Seating On Bus
405A - Gravity Flip
499B - Lecture
709A - Juicer
1358C - Celex Update
1466B - Last minute enhancements
450B - Jzzhu and Sequences